% ====================================================================
% 159.402 	Programming Languages Project 2
% 			Dynamic Maze
% ====================================================================
%	This project attempts to solve a dynamically changing maze using
%	Bratko's best first search algorithm.

% --------------------------------------------------------------------
% Maze Model
% --------------------------------------------------------------------

% node(N, ID).
%	Dynamic nodes
%	N is node name
%	ID is random function ID
node(a,0).
node(b,1).
node(c,2).
node(d,3).
node(e,4).
node(f,5).
node(g,6).
node(h,7).
node(i,8).
node(j,9).
node(k,10).
node(l,11).
node(m,12).
node(n,13).
node(o,14).
node(p,15).
node(q,16).
node(r,17).
node(s,18).
node(t,19).
node(u,20).
node(v,21).
node(w,22).
node(x,23).
node(y,24).
node(z,25).
node(aa,26).
node(ab,27).
node(ac,28).
node(ad,29).
node(ae,30).
node(af,31).
node(ag,32).
node(ah,33).
node(ai,34).
node(aj,35).
node(ak,36).
node(al,37).
node(am,38).
node(an,39).
node(ao,40).
node(ap,41).
node(aq,42).
node(ar,43).
node(as,44).
node(at,45).
node(au,46).
node(av,47).
node(aw,48).
node(ax,49).
node(ay,50).
node(az,51).
node(ba,52).
node(bb,53).
node(bc,54).
node(bd,55).
node(be,56).
node(bf,57).
node(bg,58).
node(bh,59).
node(bi,60).
node(bj,61).
node(bk,62).
node(bl,63).
node(bm,64).
node(bn,65).
node(bo,66).
node(bp,67).
node(bq,68).
node(br,69).
node(bs,70).
node(bt,71).
node(bu,72).
node(bv,73).
node(bw,74).
node(bx,75).
node(by,76).
node(bz,77).
node(ca,78).
node(cb,79).
node(cc,80).
node(cd,81).
node(ce,82).
node(cf,83).
node(cg,84).
node(ch,85).
node(ci,86).
node(cj,87).
node(ck,88).
node(cl,89).
node(cm,90).
node(cn,91).
node(co,92).
node(cp,93).
node(cq,94).
node(cr,95).
node(cs,96).
node(ct,97).
node(cu,98).
node(cv,99).
node(cw,100).
node(cx,101).
node(cy,102).
node(cz,103).
node(da,104).
node(db,105).
node(dc,106).
node(dd,107).
node(de,108).
node(df,109).
node(dg,110).
node(dh,111).
node(di,112).
node(dj,113).
node(dk,114).
node(dl,115).
node(dm,116).
node(dn,117).
node(do,118).
node(dp,119).
node(dq,120).
node(dr,121).
node(ds,122).
node(dt,123).
node(du,124).
node(dv,125).
node(dw,126).
node(dx,127).
node(dy,128).
node(dz,129).
node(ea,130).
node(eb,131).
node(ec,132).
node(ed,133).
node(ee,134).
node(ef,135).
node(eg,136).
node(eh,137).
node(ei,138).
node(ej,139).
node(ek,140).
node(el,141).
node(em,142).
node(en,143).
node(eo,144).
node(ep,145).
node(eq,146).
node(er,147).
node(es,148).
node(et,149).
node(eu,150).
node(ev,151).
node(ew,152).
node(ex,153).
node(ey,154).
node(ez,155).
node(fa,156).
node(fb,157).
node(fc,158).
node(fd,159).
node(fe,160).
node(ff,161).
node(fg,162).
node(fh,163).
node(fi,164).
node(fj,165).
node(fk,166).
node(fl,167).
node(fm,168).
node(fn,169).
node(fo,170).
node(fp,171).
node(fq,172).
node(fr,173).
node(fs,174).
node(ft,175).
node(fu,176).
node(fv,177).
node(fw,178).
node(fx,179).
node(fy,180).
node(fz,181).
node(ga,182).
node(gb,183).
node(gc,184).
node(gd,185).
node(ge,186).
node(gf,187).
node(gg,188).
node(gh,189).
node(gi,190).
node(gj,191).
node(gk,192).
node(gl,193).
node(gm,194).
node(gn,195).
node(go,196).
node(gp,197).
node(gq,198).
node(exit,199).

% node(N).
%	Static nodes
%	N is the node name
node(entrance).
node(static01).
node(static02).
node(static03).
node(static04).
node(static05).
node(static06).
node(static07).
node(static08).
node(static09).
node(static10).
node(static11).
node(static12).

% connected(N1,N2, D).
%	Connected static nodes
%	N1 must be a node
%	N2 must be a node
%	D, Distance, is randomly generated by adjacent.
connected(entrance, static01, Distance) :-
	Distance is random(10),
	node(entrance),
	node(static01).	
	
connected(static01, static02, Distance) :-
	Distance is random(10),
	node(static01),
	node(static02).	
	
connected(static01, static03, Distance) :-
	Distance is random(10),
	node(static01),
	node(static03).	
	
connected(static01, static04, Distance) :-
	Distance is random(10),
	node(static01),
	node(static04).	
	
connected(static02, static05, Distance) :-
	Distance is random(10),
	node(static02),
	node(static05).	
	
connected(static02, static06, Distance) :-
	Distance is random(10),
	node(static02),
	node(static06).	
	
connected(static03, static08, Distance) :-
	Distance is random(10),
	node(static03),
	node(static08).	
	
connected(static04, static07, Distance) :-
	node(static04),
	node(static07).	
	
connected(static05, static06, Distance) :-
	Distance is random(10),
	node(static05),
	node(static06).	
	
connected(static06, static09, Distance) :-
	Distance is random(10),
	node(static06),
	node(static09).	
	
connected(static07, static11, Distance) :-
	Distance is random(10),
	node(static07),
	node(static11).	
	
connected(static07, static12, Distance) :-
	Distance is random(10),
	node(static07),
	node(static12).	
	
connected(static09, static10, Distance) :-
	Distance is random(10),
	node(static09),
	node(static10).	
	
% connected(N1, N2, Distance).
%	Dynamically connected nodes.
%	N1 is the first node
%	N2 is the second node
connected(N1, N2, Distance) :-
	Distance is random(10),
	R2 is random(200),
	node(N2, R2).	

% adjacent(Node1, Node2).
adjacent(Node1, Node2, Distance) :-
	connected(Node1, Node2, Distance);
	connected(Node2, Node1, Distance).

% h(Node,Heuristic)
%	Heuristic estimate
h(Node,Heuristic) :-
	Heuristic is random(50).
	
% goal(Node).
%	Goal of the search algorithm
goal(exit).

% --------------------------------------------------------------------
% End Maze Model
% --------------------------------------------------------------------


% --------------------------------------------------------------------
% Debugging Functions
% --------------------------------------------------------------------

% solve(Entry,Exit).
%	Debug function to see if nodes are dynamically created
%	Does not take into account the distance between nodes
%	Entry is the chosen entrance to the maze
%	Exit is the chosen exit for the maze
solve(Entry, Exit) :-
	NodesVisited = [Entry],
	path(Entry,Exit,NodesVisited).

% path(exit, exit, NodesVisited).
%	exit is the exit
%	NodesVisited is the list of nodes visited
path(exit, exit, NodesVisited) :-
	printlist(NodesVisited).
	
% path(Entry,Exit, NodesVisited).
%	Entry is the starting point of recursion
%	Exit is the goal node
%	NodesVisited is the list of nodes visited
path(Entry, Exit, NodesVisited) :-
	adjacent(Entry, NextNode, Distance),
	not(member(NextNode, NodesVisited)),
	path(NextNode,Exit,[NextNode|NodesVisited]).
% --------------------------------------------------------------------
% End Debugging Functions
% --------------------------------------------------------------------


% --------------------------------------------------------------------
% Helper Functions
% --------------------------------------------------------------------

% member(X, List).
%	X is a member of a list (from frequent.pl), a file
%	from the paper's repository
member(X, [X|_]).		% X is the head of the list
member(X, [_|Rest]) :-
	member(X, Rest).	% X is in the tail of the list
	
% printlist(List).
%	Prints any list
printlist([]).
printlist([Head|Tail]) :- 
	printlist(Tail),
	write(Head),
	write(' ').
% --------------------------------------------------------------------
% End Helper Functions
% --------------------------------------------------------------------


% --------------------------------------------------------------------
% Best first search algorithm
% --------------------------------------------------------------------
%	From bestFirstSearch.pl
%	Bratko's code

% Figure 12.3  A best-first search program.


% bestfirst( Start, Solution): Solution is a path from Start to a goal
bestfirst(Start, Solution) :-
	expand([], l(Start, 0/0), 9999, _, yes, Solution).
	%  Assume 9999 is greater than any f-value

% expand( Path, Tree, Bound, Tree1, Solved, Solution):
%   Path is path between start node of search and subtree Tree,
%   Tree1 is Tree expanded within Bound,
%   if goal found then Solution is solution path and Solved = yes

%  Case 1: goal leaf-node, construct a solution path

expand(P, l(N, _), _, _, yes, [N|P])  :-
	goal(N).

%  Case 2: leaf-node, f-value less than Bound
%  Generate successors and expand them within Bound.

expand(P, l(N,F/G), Bound, Tree1, Solved, Sol)  :-
	F  =<  Bound,
	(bagof(M/C, (adjacent(N,M,C), not(member(M,P)) ), Succ), 
     !,                                   % Node N has successors
     succlist(G, Succ, Ts),               % Make subtrees Ts
     bestf(Ts, F1),                       % f-value of best successor
     expand(P, t(N,F1/G,Ts), Bound, Tree1, Solved, Sol)
     ;
     Solved = never                       % N has no successors - dead end
	) .

%  Case 3: non-leaf, f-value less than Bound
%  Expand the most promising subtree; depending on 
%  results, procedure continue will decide how to proceed

expand(P, t(N,F/G,[T|Ts]), Bound, Tree1, Solved, Sol)  :-
  F  =<  Bound,
  bestf(Ts, BF), min(Bound, BF, Bound1),          % Bound1 = min(Bound,BF)
  expand([N|P], T, Bound1, T1, Solved1, Sol),
  continue(P, t(N,F/G,[T1|Ts]), Bound, Tree1, Solved1, Solved, Sol).

%  Case 4: non-leaf with empty subtrees
%  This is a dead end which will never be solved

expand(_, t(_,_,[]), _, _, never, _) :- !.

%  Case 5:  f-value greater than Bound
%  Tree may not grow.

expand(_, Tree, Bound, Tree, no, _)  :-
  f(Tree, F), F > Bound.

% continue( Path, Tree, Bound, NewTree, SubtreeSolved, TreeSolved, Solution)

continue(_, _, _, _, yes, yes, Sol).

continue(P, t(N,F/G,[T1|Ts]), Bound, Tree1, no, Solved, Sol)  :-
	insert(T1, Ts, NTs),
	bestf(NTs, F1),
	expand(P, t(N,F1/G,NTs), Bound, Tree1, Solved, Sol).

continue(P, t(N,F/G,[_|Ts]), Bound, Tree1, never, Solved, Sol)  :-
	bestf(Ts, F1),
	expand(P, t(N,F1/G,Ts), Bound, Tree1, Solved, Sol).

% succlist( G0, [ Node1/Cost1, ...], [ l(BestNode,BestF/G), ...]):
%   make list of search leaves ordered by their F-values

succlist(_, [], []).

succlist(G0, [N/C | NCs], Ts)  :-
	G is G0 + C,
	h(N, H),                             % Heuristic term h(N)
	F is G + H,
	succlist(G0, NCs, Ts1),
	insert(l(N,F/G), Ts1, Ts).

% Insert T into list of trees Ts preserving order w.r.t. f-values

insert(T, Ts, [T | Ts])  :-
	f(T, F), bestf(Ts, F1),
	F  =<  F1, !.

insert(T, [T1 | Ts], [T1 | Ts1])  :-
	insert(T, Ts, Ts1).


% Extract f-value

f(l(_,F/_), F).        % f-value of a leaf

f(t(_,F/_,_), F).      % f-value of a tree

bestf([T|_], F)  :-    % Best f-value of a list of trees
	f(T, F).

bestf([], 9999).       % No trees: bad f-value
  
min(X, Y, X)  :-
	X  =<  Y, !.

min(X, Y, Y).

% --------------------------------------------------------------------
% End Bratko's Best First Search Algorithm
% --------------------------------------------------------------------
% ====================================================================